# -*- coding:utf-8 -*-
__author__ = 'gin.chen'
from binary_tree import BinaryTree


class MinHeap:

    def __init__(self):
        self.count = 0
        self.data = [self.count]

    def size(self):
        return self.count

    def is_empty(self):
        return self.count == 0

    def insert(self, item):
        self.data.append(item)
        self.count += 1
        self.shift_up(self.count)

    def shift_up(self, k):
        while k > 1 and self.data[k] < self.data[k / 2]:
            self.data[k], self.data[k / 2] = self.data[k / 2], self.data[k]
            k /= 2

    def get_heap(self):
        return self.data


if __name__ == '__main__':
    data = [9, 3, 7, 6, 5, 1, 10, 2]
    mh = MinHeap()
    for i in data:
        mh.insert(i)
    data = mh.get_heap()
    data.pop(0)
    BinaryTree(data).printTrave()
